1. Field of the Invention
The present invention relates to an image processing apparatus, an image processing method, and a storage medium.
2. Description of the Related Art
Conventionally, a rendering method that extracts outline information (also referred to as edge information) from coordinates information of a figure and forms an image based on the outline information is widely used in order to draw a figure. Such a method is discussed in Japanese Patent Application Laid-Open No. 4-170686. The outline information is expressed by straight lines. A digital differential analyzer (DDA) algorithm is a known graphics algorithm used for rasterization of lines (see David Rogers, “Procedural Elements for Computer Graphics” McGraw-Hill Education).
FIG. 1 illustrates an example of conventional renderer processing. In FIG. 1, an input figure is divided into bands before it is processed. A typical problem in graphics processing that occurs in such system is the reduction of the rendering speed when many graphic objects are input. Japanese Patent Application Laid-Open No. 2003-51019 discusses a method for increasing the processing speed by dividing input figures into bands as illustrated in FIG. 1 and assigning an independent processing unit (thread) to each band.
According to a conventional renderer, edge data of a scan line is generated at the time when coordinates information or line segment information such as a path of the figure is transferred to the renderer. Thus, each figure cannot be independently processed. On the other hand, if a figure is divided into band units, parallel processing can be performed since each region is independent. According to this method, the execution of parallel processing can be efficiently performed under certain conditions. However, not all cases can be efficiently processed.
For example, if one figure exists in two adjacent band regions A and B arranged one above the other, parallel processing cannot be executed in that state. In order to perform processing in such a state, it is necessary to supply the figure (replicate data of the figure and transfer the obtained data) to each of the two band regions. Thus, sufficient high speed processing cannot be expected if Page Description Language (PDL) data including a number of figures at the band boundary regions is processed by band parallel processing. Although it is possible to adjust the break position of the bands considering the arrangement of the objects, since there will be figures on the border of regions regardless of the adjustment, it will not fundamentally solve the problem
Further, if only one thread can be assigned to one band as a basic unit of processing, and if the distribution of objects is extremely unbalanced (e.g. several hundreds of objects in one band), high speed processing cannot be expected.